package com.njupt.Array;

import java.util.HashMap;

/**
 * 76. 最小覆盖子串
 */
public class MinWindow {


    public String minWindow1(String s, String t) {
        if (s.length()<t.length()){
            return "";
        }
        HashMap<Character, Integer> tMap = new HashMap<>();
        HashMap<Character, Integer> sMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tMap.put(t.charAt(i),
                    tMap.getOrDefault(t.charAt(i),0)+1);
        }
        int minLeft = -1;
        int minRight = -1;
        int minLen = s.length()+1;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            sMap.put(s.charAt(right),
                    sMap.getOrDefault(s.charAt(right),0)+1);
            while(isContainString1(sMap,tMap)){
                if(right-left +1<minLen){
                    minLen = right-left +1;
                    minLeft = left;
                    minRight = right;
                }
                sMap.put(s.charAt(left),
                        sMap.get(s.charAt(left))-1);
                if(sMap.get(s.charAt(left)) == 0){
                    sMap.remove(s.charAt(left));
                }
                left++;
            }

        }
        return (minLeft==-1 || minRight==-1)? "" :  s.substring(minLeft,minRight+1);
    }

    private boolean isContainString1(HashMap<Character, Integer> sMap, HashMap<Character, Integer> tMap) {
        for (Character c : tMap.keySet()) {
            if(!sMap.containsKey(c)){
                return false;
            }else {
                if(tMap.get(c)>sMap.get(c)){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * b暴力解法，超出时间限制
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        if (s.length()<t.length()){
            return "";
        }
        HashMap<Character, Integer> tMap = new HashMap<>();
        HashMap<Character, Integer> sMap = new HashMap<>();
        int minLeft = -1;
        int minRight = -1;
        int minLen = s.length()+1;
        for (int i = 0; i < t.length(); i++) {
            tMap.put(t.charAt(i),
                    tMap.getOrDefault(t.charAt(i),0)+1);
        }

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j <s.length() ; j++) {
                if(isContainString(s.substring(i,j+1),sMap,tMap)){
                    if(j-i+1<minLen){
                        minLen = j-i+1;
                        minLeft = i;
                        minRight = j;
                    }
                }
                sMap.clear();
            }
        }
        return  (minLeft==-1 || minRight==-1)? "" :  s.substring(minLeft,minRight+1);

    }

    private Boolean isContainString(String substring, HashMap<Character, Integer> sMap, HashMap<Character, Integer> tMap) {
        for (int i = 0; i < substring.length(); i++) {
            sMap.put(substring.charAt(i),
                    sMap.getOrDefault(substring.charAt(i),0)+1);
        }

        for (Character c : tMap.keySet()) {
            if(!sMap.containsKey(c)){
                return false;
            }else {
                if(tMap.get(c) > sMap.get(c)){
                    return false;
                }
            }
//            if(sMap.containsKey(c) && tMap.get(c) <= sMap.get(c))
        }
        return true;

    }

    public static void main(String[] args) {
        String s = "cabwefgewcwaefgcf";
        String t = "cae";
        MinWindow test = new MinWindow();
        System.out.println(test.minWindow1(s, t));
    }
}
